// 给定两个字符串 text1 和 text2，
// 返回这两个字符串的最长 公共子序列 的长度。
// 如果不存在 公共子序列 ，返回 0 。
// 一个字符串的 子序列是指这样一个新的字符串：
// 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（
// 也可以不删除任何字符）后组成的新字符串。
// 例如，"ace" 是 "abcde" 的子序列，
// 但 "aec" 不是 "abcde" 的子序列。
// 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/longest-common-subsequence
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const len1 = text1.length
  const len2 = text2.length

  const dp = new Array(len1).fill(0).map(() => new Array(len2).fill(0))

  dp[0][0] = (text1[0] === text2[0]) ? 1 : 0
  for (let i = 1; i < len1; i++) {
    dp[i][0] = dp[i - 1][0] + (text1[i] === text2[0]) ? 1 : 0
  }
  for (let i = 1; i < len2; i++) {
    dp[0][i] = dp[0][i - 1] + (text1[0] === text2[i]) ? 1 : 0
  }

  for (let i = 1; i < len1; i++) {
    for (let j = 1; j < len2; j++) {
      let p1 = 0
      let p2 = 0
      let p3 = 0
      if (text1[i] === text2[j]) {
        p1 = dp[i - 1][j - 1] + 1
      } else {
        p2 = dp[i - 1][j]
        p3 = dp[i][j - 1]
      }

      dp[i][j] = Math.max(p1, p2, p3)
    }
  }

  return dp[len1 - 1][len2 - 1]
}

console.log(
  longestCommonSubsequence("ezupkr",
"ubmrapg")
)






